﻿// 3628. 边的删减.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/3631/

给定一个由 n
 个点和 m
 条边组成的无向连通加权图。

设点 1
 到点 i
 的最短路径长度为 di
。

现在，你需要删掉图中的一些边，使得图中最多保留 k
 条边。

如果在删边操作全部完成后，点 1
 到点 i
 的最短路径长度仍为 di
，则称点 i
 是一个优秀点。

你的目标是通过合理进行删边操作，使得优秀点的数量尽可能大。

输入格式
第一行包含三个整数 n,m,k
。

接下来 m
 行，每行包含三个整数 x,y,w
，表示点 x
 和点 y
 之间存在一条长度为 w
 的边。

保证给定无向连通图无重边和自环。

输出格式
第一行包含一个整数 e
，表示保留的边的数量 (0≤e≤k)
。

第二行包含 e
 个不同的 1∼m
 之间的整数，表示所保留的边的编号。

按输入顺序，所有边的编号从 1
 到 m
。

你提供的方案，应使得优秀点的数量尽可能大。

如果答案不唯一，则输出任意满足条件的合理方案均可。

数据范围
对于前五个测试点，2≤n≤15,1≤m≤15
。
对于全部测试点，2≤n≤105,1≤m≤105,n−1≤m,0≤k≤m,1≤x,y≤n,x≠y,1≤w≤109
。

输入样例1：
3 3 2
1 2 1
3 2 1
1 3 3
输出样例1：
2
1 2
输入样例2：
4 5 2
4 1 8
2 4 1
2 1 3
3 4 9
3 1 5
输出样例2：
2
3 2
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}
 